package metrictree.functors.impls;

public class StringMetrics {

	/**
	 * Levenshtein Distance is an algorithm that gives you the minium number of
	 * edits necessary to transform one sequence into another It considers 3
	 * kinds of operations: insertions, deletion, and substitution
	 * 
	 * This algorithm was coded from the PseudoCode provided on Wikipedia
	 * http://en.wikipedia.org/wiki/Levenshtein_Distance
	 * http://www.merriampark.com/ld.htm http://www.merriampark.com/ldjava.htm
	 * 
	 * @param s
	 * @param t
	 * @return
	 */
	public static float getLevenshteinDistance(String s, String t) {
		if (s == null || t == null) {
			throw new IllegalArgumentException("Strings must not be null");
		}

		int n = s.length(); // length of s
		int m = t.length(); // length of t

		if (n == 0) {
			return m;
		} else if (m == 0) {
			return n;
		}

		int p[] = new int[n + 1]; // 'previous' cost array, horizontally
		int d[] = new int[n + 1]; // cost array, horizontally
		int swap[]; // placeholder to assist in swapping p and d

		// indexes into strings s and t
		int i; // iterates through s
		int j; // iterates through t

		char t_j; // jth character of t

		int cost; // cost

		for (i = 0; i <= n; i++) {
			p[i] = i;
		}

		for (j = 1; j <= m; j++) {
			t_j = t.charAt(j - 1);
			d[0] = j;

			for (i = 1; i <= n; i++) {
				cost = s.charAt(i - 1) == t_j ? 0 : 1;
				// minimum of cell to the left+1, to the top+1, diagonally left
				// and up +cost
				d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1]
						+ cost);
			}

			// copy current distance counts to 'previous row' distance counts
			swap = p;
			p = d;
			d = swap;

		}

		// our last action in the above loop was to switch d and p, so p now
		// actually has the most recent cost counts
		return p[n];
	}

	public static int longestSubstr(String s, String t) {
		if (s.isEmpty() || t.isEmpty()) {
			return 0;
		}

		int m = s.length();
		int n = t.length();
		int cost = 0;
		int maxLen = 0;
		int[] p = new int[n];
		int[] d = new int[n];
		int[] swap;

		for (int i = 0; i < n; ++i) { // init. the previous row
			p[i] = 0;
		}

		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				// calculate cost/score
				if (s.charAt(i) != t.charAt(j)) {
					cost = 0;
				} else {
					if ((i == 0) || (j == 0)) {
						cost = 1;
					} else {
						cost = p[j - 1] + 1;
					}
				}
				d[j] = cost;

				if (cost > maxLen) {
					maxLen = cost;
				} else {
					maxLen = maxLen;
				}
			} // for {}

			swap = p;
			p = d;
			d = swap;
		}

		return maxLen;
	}

}
